Methods of asymmetric cryptography allow information to be very securely encrypted. A user has a public and a private key. Usually, the private key is known only to the user, whereas the public key is made public like a telephone number and used by third parties to encrypt messages to the user. Usually, publication is done either by the user himself/herself or by key distribution centers, so-called “trusted third parties” (TTP) or “Trust Centers”. Such methods are also known by the name of public key methods.
In order to encrypt a message, a sender uses the public key which is assigned to a user or recipient and which the sender can load from a key distribution center, for example, over the Internet. The message encrypted in this manner can then be decrypted only by a person who possesses the private key matching the public key of the recipient.
One of the best-known asymmetric cryptographic methods is the RSA method, which is named by its inventors Rivest, Shamir and Adleman. The high security of the RSA method is based on the difficulty of the factoring problem: it is, in fact, easy to find and multiply together two large prime numbers (this product is called RSA number), but it is virtually impossible to find the prime factors if only the RSA number is known.
A public key öS generated using the RSA method is composed of two parts (öS1, öS2). The first part öS1 of a public key is the RSA number. The second part öS2 is a random number which must be relatively prime to (a-1) (b-1), if a, b are the two prime numbers mentioned. A private key pS matching the public key öS is calculated by the following equation: pS*öS2=1 mod ((a-1) (b-1)). Calculation of private key pS from public key öS is similarly difficult and involved as the above-mentioned decomposition of a product into its prime factors. Because of this, a private key can be calculated from the associated public key only with great computational effort.
For encryption, the RSA method uses the following formula: c=möS2 mod öS1, where m is a plaintext message and c is the encrypted message. Decryption is done using the formula: m=cpS mod öS1. RSA number öS1 is used in both formulas.
Despite the very high security standards of the RSA method, this method, like all other methods of asymmetric cryptography, has the disadvantage that a sender who wishes to encrypt a message to a recipient must either already know the public key or request it from a key distribution center.
For example, in the known, now widespread program PGP (Pretty Good Privacy), which is based on RSA, public keys are distributed through special Internet sites. A sender can obtain the public key of a recipient from such an Internet site via the Internet, provided that the public key has been escrowed there by the recipient. The transfer of a public key can also accomplished via e-mail or using electronic data carriers such as diskettes.
However, such ways of transferring a public key hold essentially two disadvantages: If the key distribution center fails, it is impossible for the sender to load the public key of the recipient. For example, a server failure in the key distribution center could considerably affect the distribution of public keys. Similar is true for the transfer via e-mail. If an e-mail server fails, no more public keys can be transferred here either.
A further disadvantage, which occurs especially when obtaining public keys via the Internet, is that there is no absolute certainty about the authenticity of the key distribution center. In particular, there is no guarantee that the public keys distributed by the key distribution center are actually assigned to the specified recipients. For instance, it would be conceivable that, after a request for a public key via the Internet, an untrustworthy Internet site pretends to be a key distribution center and transmits an false public key, faking a particular recipient. When transferring a public key via e-mail, misuse is also possible through manipulation.
To circumvent this problem, A. Shamir proposed in his essay “Identity-Based crypto Systems and Signature Schemes”, Crypto 1984, LNCS 196, Springer-Verlag, 47-53, 1985, that unique data identifying a recipient be used as the public key instead of generating public and private keys and publishing the public key. The examples given by A. Shamir for this unique data include the recipient name, the network address of his/her computer, his/her social security number, his/her address, office number or telephone number, or a combination of such data. The only condition is that the data uniquely identifies the recipient.
In order to send an encrypted message to a recipient, a sender must sign the message with his/her own private key; the signed message being encrypted using data uniquely identifying the recipient, such as his/her name and the network address of his/her computer. The recipient decrypts the received message using his/her own private key and verifies the signature of the sender using the name and the network address of the computer of the sender as a verification key. Here, the risk of misuse is lower than with pure public key systems, since the identification data of the sender and recipient provides at least some degree of confidentiality.
However, to implement the method proposed by A. Shamir, a central authority must generate the private keys for each user. Therefore, to prevent misuse, A Shamir proposes to distribute so-called “smart cards” to the users, the smart cards containing the particular private key of a user. Thus, unlike the encryption methods mentioned at the outset, the generation of keys does not lie in the hands of the user, but is carried out by a central authority. However, this involves an enormous administrative effort. Moreover, the central authority cannot be simply designed as an Internet site only for distributing public keys, but has to centrally generate keys for users and transmit the keys to these users. In the case of the smart card concept, this proposal is also extremely cost-intensive. It is also questionable whether such a smart card would be widely accepted because a not inconsiderable investment in equipment for reading the smart card would be required at the user end.